import math

class Solution:

    cache = {1: False}

    def divisorGame(self, N: int) -> bool:
        # 得到N所有可能的因子
        candidates = (N - i for i in range(1, int(math.sqrt(N))+1) if N % i == 0 and i < N)
        for n in candidates:
            # 对每个因子i回溯求N-i的输赢结果
            if self.cache.get(n) is None:
                result = self.divisorGame(n)
                self.cache[n] = result
            # 只要有一种对手会输的选法，则爱丽丝必赢
            if self.cache[n] is False:
                return True
        return False